#pragma once
#include <vector>
#include <list>
#include <string>
#include <sstream>
#include <deque>
#include <iostream>
#include <algorithm>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
	{
	}
};

static std::vector<std::string> split(const std::string &s, char delimiter)
{
	std::vector<std::string> tokens;
	std::string token;
	std::istringstream tokenStream(s);
	while (std::getline(tokenStream, token, delimiter))
	{
		token.erase(remove(token.begin(), token.end(), ' '), token.end());
		tokens.push_back(token);
	}
	return tokens;
}

TreeNode *CreatTree(const string dataStr, const string nullTag)
{
	string datacpy = dataStr;
	size_t index = string::npos;
	while ((index = datacpy.find('[')) != string::npos)
		datacpy.erase(index, 1);
	while ((index = datacpy.find(']')) != string::npos)
		datacpy.erase(index, 1);
	auto tokens = split(datacpy, ',');

	TreeNode *root = new TreeNode(stoi(tokens[0]));
	list<TreeNode *> nodes;
	nodes.push_back(root);
	auto it = tokens.begin() + 1;
	auto node = nodes.begin();
	for (;; node++)
	{
		if (it == tokens.end())
			break;
		(*node)->left = (*it == nullTag) ? nullptr : new TreeNode(stoi(*it));
		it++;
		if ((*node)->left)
			nodes.push_back((*node)->left);

		if (it == tokens.end())
			break;
		(*node)->right = (*it == nullTag) ? nullptr : new TreeNode(stoi(*it));
		it++;
		if ((*node)->right)
			nodes.push_back((*node)->right);
	}
	return root;
}

void PrintTreeByWide(TreeNode *root, string nullTag, int level)
{
	cout << "[";
	deque<TreeNode *> nodes;
	nodes.push_back(root);
	for (int i = 0; i < level; i++)
	{
		for (int j = 0; j < (1 << i); j++)
		{
			TreeNode *node = nodes.front();
			if (node == nullptr)
			{
				cout << nullTag << ",";
			}
			else
			{
				cout << node->val << ",";
				nodes.push_back(node->left);
				nodes.push_back(node->right);
			}
			nodes.pop_front();
		}
	}
	cout << "]" << endl;
}